#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>
using namespace std;
int minFallingPathSum(vector<vector<int>>& matrix) {
    int row = matrix.size(); int col = matrix[0].size();
    vector<vector<int>> dp(row, vector<int>(col));
    int i = 0; int j = 0;
    if (row == 1)return matrix[0][0];
    while (j < col) { dp[0][j] = matrix[0][j]; ++j; }
    for (i = 1; i < row; i++)
    {
        for (j = 0; j < col; j++)
        {
            if (j == 0)
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i-1][j + 1]);
            else if (j == col - 1)
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j]);
            else
                dp[i][j] = matrix[i][j] + min(min(dp[i - 1][j], dp[i - 1][j - 1]), min(dp[i - 1][j], dp[i - 1][j + 1]));
        }

    }
    int tmp = dp[row - 1][j]; j = 0;
    while (j < col) { if (tmp > dp[row - 1][j])tmp = dp[row - 1][j]; ++j; }
    return tmp;
}
int main()
{
    vector<vector<int>> v1(3, vector<int>(3)); int arr[9] = { 2,1,3,6,5,4,7,8,9 }; int i = 0;
    int m = 0; int n = 0;
    while (m < 3)
    {
        for (n=0;n < 3;)
        {
            v1[m][n] = arr[i]; ++i; ++n;
        }
        ++m;
    }

    minFallingPathSum(v1);
}